package com.henry.base.sort;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class BitVetory {
    private int count;
    private int[] a;
    private int BIT_LENGTH=32;
    private int P;
    private int S;
    private int MASK=0x1f;
    private int SHIFT=5;

    public BitVetory(int count) {
        this.count=count;
        a = new int[(count - 1) / BIT_LENGTH + 1];
    }
    public void set(int i){
        P=i>>SHIFT;
        S=i&MASK;
        a[P] |= 1<<S;
    }

    public int get(int i) {
        P=i>>SHIFT;
        S=i&MASK;
//        return Integer.bitCount((a[P]>>S) & 1);
        return Integer.bitCount(a[P] & (1<<S));
    }

    public void clear(int i) {
        P=i>>SHIFT;
        S=i&MASK;
        a[P] &= ~(1 << S);
    }

    public List<Integer> getSortedArray() {
        ArrayList<Integer> sortedArray = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            if (get(i) == 1) { //判断i是否存在
                sortedArray.add(i);
            }
        }
        return sortedArray;
    }



    private static List<Integer> getRandomList(int count) {
        Random random = new Random();
        ArrayList<Integer> randoms = new ArrayList<>();
        int k=0;
        while (k < (count-1)) {
            k++;
            int element = random.nextInt(count - 1) + 1;
            if(!randoms.contains(element)){
                randoms.add(element);
            }
        }
        System.out.println("k:"+k);
        return randoms;
    }


    public static void main(String[] args) {
        int count = 25;
        List<Integer> randoms = getRandomList(count);
        System.out.println("排序前：");
        BitVetory bitVetory = new BitVetory(count);
        for (Integer e : randoms) {
            System.out.print(e+",");
            bitVetory.set(e);
        }

        List<Integer> sortedArray = bitVetory.getSortedArray();
        System.out.println("\r\n**************************");
        System.out.println("排序后：");
        for (Integer e : sortedArray) {
            System.out.print(e+",");
        }

    }
}
